package algorithm;

public class BinarySort {
    public static void main(String[] args) {
        //int[] arr = {1,4,5,7,10,13};
        //System.out.println(close2(arr,14));
        // System.out.println(binarySearch2(arr, 13));
        //int[] arr = {1,4,4,5,7,10,10,13};
        //System.out.println(findLast2(arr, 4));
        //System.out.println(findLast(arr,4));
        int[][] arr2 = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
        findInArr(arr2, 4, 4, 9);
    }

    public static boolean findInArr(int[][] arr, int row, int column, int target) {
        int i = column - 1, j = 0;
        while (i >= 0 && j < column) {
            if (arr[i][j] == target) {
                System.out.println("i ="+i+ " j = " + j);
                return true;
            }
            if (arr[i][j] > target) {
                i--;
            }
            if (arr[i][j] < target) {
                j++;
            }
        }
        return false;
    }

    public static int findFirst2(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (low < arr.length && arr[low] == target) {
            return low;
        }
        return -1;
    }

    public static int findLast2(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (high < arr.length && arr[high] == target) {
            return high;
        }
        return -1;
    }

    public static int close2(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low < high - 1) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] == target) {
                return arr[mid];
            } else if (arr[mid] > target) {
                high = mid;
            }else {
                low = mid;
            }
        }
        if (arr[low] > target) {
            return arr[low];
        }
        if (arr[high] < target) {
            return arr[high];
        }
        return (target - arr[low] > arr[high] - target ? arr[high] : arr[low]);
    }


    public static int binarySearch2(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }


    public static boolean binaryArrSearch(int[][] arr, int row, int column, int target) {
        // 从左下角开始查找
        int i = row - 1, j = 0;
        while (i >= 0 && j < column) {
            int num = arr[i][j];
            if (num== target) {
                System.out.println("i +"+i + " j = " + j);
                return true;
            }
            if (num > target) {
                // 数字大于目标，排除下面的行
                i--;
            }else {
                // 数字小于目标，排除左边的列
                j++;
            }
        }
        return false;
    }

    public static int binarySearch(int[] arr, int target) {
        int low = 0, mid,high = arr.length - 1;
        // [low,high] mid
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                high = mid-1;
            }else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 找到最接近的数
    public static int close(int[] arr, int target) {
        int low= 0, mid, high = arr.length - 1;
        while (low < high - 1) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                high = mid;
            }else {
                low = mid;
            }
        }
        if (arr[low] > target) {
            return arr[low];
        }
        if (arr[high] < target) {
            return arr[high];
        }
        return (arr[high] - target > target-arr[low])? arr[low] : arr[high];
    }

    public static int findFirst(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (low<arr.length&&arr[low] == target) {
            return low;
        }
        return -1;
    }

    public static int findLast(int[] arr, int target) {
        int low = 0, mid, high = arr.length - 1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        if (high<arr.length&&arr[high] == target) {
            return high;
        }
        return -1;
    }
}
